package sort;

import java.util.Arrays;

/**
 * 并归排序算法
 * @author Tang Jiujia
 * @since 11:10 2020-04-13
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] numbers = {2, 5, 8, 3, 7, 5, 15, 9, 11, 6};
        sort(numbers);
        System.out.println(Arrays.toString(numbers));
    }

    /**
     * 排序方法
     *
     * @param numbers 待排序数组
     */
    private static void sort(int[] numbers) {
        int len = numbers.length;
        int[] temp = new int[len];
        mergeSort(numbers, 0, len - 1, temp);
    }

    /**
     * 采用并归方式进行排序
     *
     * @param numbers 待排数组
     * @param left	左索引
     * @param right	右索引
     * @param temp 临时工
     */
    private static void mergeSort(int[] numbers, int left, int right, int[] temp) {
        if (left >= right) {return;}
        int mid = (left + right) / 2;
        mergeSort(numbers, left, mid, temp);
        mergeSort(numbers, mid + 1, right, temp);
        merge(numbers, left, mid, right,temp);
    }

    /**
     * 合并、排序操作
     *
     * @param numbers
     * @param left
     * @param right
     * @param temp
     */
    private static void merge(int[] numbers, int left, int mid, int right, int[] temp) {
        //右指针
        int i = left;
        //左指针
        int j = mid + 1;
        //临时数组指针
        int t = 0;

        while (i <= mid && j <= right) {
            if (numbers[i] <= numbers[j]) {
                temp[t++] = numbers[i++];
            } else {
                temp[t++] = numbers[j++];
            }
        }
        //将左边剩余的元素填入temp
        while (i <= mid) {
            temp[t++] = numbers[i++];
        }
        //将右边剩余的元素填入temp
        while (j <= right) {
            temp[t++] = numbers[j++];
        }
        t = 0;
        //将temp中的元素全部copy到原数组中
        while (left <= right) {
            numbers[left++] = temp[t++];
        }
    }
}


